"""
LeetCode 第 1 题：两数之和 (Two Sum)
难度：简单

题目链接：
- 中文版：https://leetcode-cn.com/problems/two-sum/
- 英文版：https://leetcode.com/problems/two-sum/

题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出
和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里
不能重复出现。

示例 1:
    输入: nums = [2,7,11,15], target = 9
    输出: [0,1]
    解释: 因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2:
    输入: nums = [3,2,4], target = 6
    输出: [1,2]

示例 3:
    输入: nums = [3,3], target = 6
    输出: [0,1]
"""

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        方法：哈希表（最优解）
        
        时间复杂度：O(n)
        空间复杂度：O(n)
        
        思路：
        1. 使用字典存储已遍历的数字及其索引
        2. 对于当前数字，计算需要的补数 (target - num)
        3. 如果补数已在字典中，返回结果
        4. 否则，将当前数字存入字典
        """
        seen = {}  # 存储 {数值: 索引}
        
        for i, num in enumerate(nums):
            complement = target - num  # 计算补数
            
            if complement in seen:
                # 找到答案：返回补数索引和当前索引
                return [seen[complement], i]
            
            # 将当前数字存入字典
            seen[num] = i
        
        # 如果没找到（题目保证有解，这行不会执行）
        return []


# ==================== 本地测试 ====================
def test_solution():
    """本地测试用例"""
    solution = Solution()
    
    # 测试用例 1
    nums1 = [2, 7, 11, 15]
    target1 = 9
    result1 = solution.twoSum(nums1, target1)
    assert result1 == [0, 1], f"测试 1 失败: 期望 [0, 1]，实际 {result1}"
    print(f"✓ 测试 1 通过: nums={nums1}, target={target1} → {result1}")
    
    # 测试用例 2
    nums2 = [3, 2, 4]
    target2 = 6
    result2 = solution.twoSum(nums2, target2)
    assert result2 == [1, 2], f"测试 2 失败: 期望 [1, 2]，实际 {result2}"
    print(f"✓ 测试 2 通过: nums={nums2}, target={target2} → {result2}")
    
    # 测试用例 3
    nums3 = [3, 3]
    target3 = 6
    result3 = solution.twoSum(nums3, target3)
    assert result3 == [0, 1], f"测试 3 失败: 期望 [0, 1]，实际 {result3}"
    print(f"✓ 测试 3 通过: nums={nums3}, target={target3} → {result3}")
    
    # 测试用例 4：边界情况
    nums4 = [-1, -2, -3, -4, -5]
    target4 = -8
    result4 = solution.twoSum(nums4, target4)
    assert result4 == [2, 4], f"测试 4 失败: 期望 [2, 4]，实际 {result4}"
    print(f"✓ 测试 4 通过: nums={nums4}, target={target4} → {result4}")
    
    print("\n🎉 所有测试通过！")


if __name__ == "__main__":
    test_solution()


